import java.util.ArrayList;
import java.util.List;

public class Solution872 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public boolean leafSimilar(TreeNode root1, TreeNode root2) {
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>();
        dfs(root1,list1);
        dfs(root2,list2);
        boolean flag=true;
        for (int i=0;i<Math.min(list1.size(),list2.size());i++){
            if (list1.get(i)!=list2.get(i)){
                flag=false;
                break;
            }
        }
        return list1.size()==list2.size() && flag;
    }

    void dfs(TreeNode treeNode,List<Integer> ans){
        if (treeNode==null){
            return;
        }
        if (treeNode.left==null && treeNode.right==null){
            ans.add(treeNode.val);
            return;
        }
        dfs(treeNode.left,ans);
        dfs(treeNode.right,ans);
    }

    public static void main(String[] args) {
        TreeNode n1=new TreeNode(3,new TreeNode(5,new TreeNode(6),new TreeNode(2,new TreeNode(7),new TreeNode(4))),new TreeNode(1,new TreeNode(9),new TreeNode(8)));
        TreeNode n2=new TreeNode(3,new TreeNode(5,new TreeNode(6),new TreeNode(7)),new TreeNode(1,new TreeNode(4),new TreeNode(2,new TreeNode(9),new TreeNode(8))));
        System.out.println(new Solution872().leafSimilar(n1,n2));
    }
}
